/*
题目链接:https://leetcode.cn/problems/count-the-number-of-powerful-integers/?envType=daily-question&envId=2025-04-10
*/
//题解代码:
/*
class Solution {
public:
    #define ll long long
    int len(int x){
        int ret = 1;
        x /= 10;
        while(x){
            ret++;
            x /= 10;
        }
        return ret;
    }
    //填到数字第i位
    //limit : 每位数字一定不超过limit
    //s : 待匹配的后缀
    //free : 是否受num的约束
    //flag : 高位是否已经填过数字了
    ll dp[16][2][2];
    ll f(ll num,int i,const int limit,const string& s,int free,int flag){
        if(i<0) return 1;
        if(dp[i][free][flag] != -1) return dp[i][free][flag];
        ll ret = 0;
        int cur = (num / (ll)pow(10,i)) % 10;
        if(i<s.size()){ //与s后缀匹配的范围
            if(flag == 0 && i<s.size()-1) return 0; 
            int x = s[s.size()-1-i]-'0';
            if(free){
                if(x > limit) return 0;
                ret += f(num,i-1,limit,s,1,1);
            }else{
                if(x > min(limit,cur)) return 0;
                ret += f(num,i-1,limit,s,x<cur,1);
            }
        }else{//不在后缀匹配范围
            if(free){
                for(int x=1;x<=limit;++x){
                    ret += f(num,i-1,limit,s,1,1);
                }
                if(flag==1) ret += f(num,i-1,limit,s,1,1); 
                else ret += f(num,i-1,limit,s,1,0);
            }else{
                if(flag){
                    for(int x=0;x<min(limit,cur);++x){
                        ret += f(num,i-1,limit,s,1,1);
                    }
                    if(cur<=limit) ret += f(num,i-1,limit,s,0,1);
                    else ret += f(num,i-1,limit,s,1,1);
                }else{
                    ret += f(num,i-1,limit,s,1,0);
                    for(int x=1;x<min(limit,cur);++x){
                        ret += f(num,i-1,limit,s,1,1);
                    }
                    if(cur<=limit) ret += f(num,i-1,limit,s,0,1);
                    else ret += f(num,i-1,limit,s,1,1);
                }
            }
        }
        dp[i][free][flag] = ret;
        return ret;
    }
    long long numberOfPowerfulInt(long long start, long long finish, int limit, string s) {
        memset(dp,-1,sizeof(dp));
        return f(finish,len(finish)-1,limit,s,0,0) - f(start-1,len(start-1)-1,limit,s,0,0);
    }
};
*/
class Solution {
public:
    long long numberOfPowerfulInt(long long start, long long finish, int limit, string s) {
        string low = to_string(start);
        string high = to_string(finish);
        int n = high.size();
        low = string(n - low.size(), '0') + low; // 补前导零，和 high 对齐
        int diff = n - s.size();

        vector<long long> memo(n, -1);
        auto dfs = [&](this auto&& dfs, int i, bool limit_low, bool limit_high) -> long long {
            if (i == low.size()) {
                return 1;
            }

            if (!limit_low && !limit_high && memo[i] != -1) {
                return memo[i]; // 之前计算过
            }

            // 第 i 个数位可以从 lo 枚举到 hi
            // 如果对数位还有其它约束，应当只在下面的 for 循环做限制，不应修改 lo 或 hi
            int lo = limit_low ? low[i] - '0' : 0;
            int hi = limit_high ? high[i] - '0' : 9;

            long long res = 0;
            if (i < diff) { // 枚举这个数位填什么
                for (int d = lo; d <= min(hi, limit); d++) {
                    res += dfs(i + 1, limit_low && d == lo, limit_high && d == hi);
                }
            } else { // 这个数位只能填 s[i-diff]
                int x = s[i - diff] - '0';
                if (lo <= x && x <= hi) { // 题目保证 x <= limit，无需判断
                    res = dfs(i + 1, limit_low && x == lo, limit_high && x == hi);
                }
            }

            if (!limit_low && !limit_high) {
                memo[i] = res; // 记忆化 (i,false,false)
            }
            return res;
        };
        return dfs(0, true, true);
    }
};
